Méthodes de Monte Carlo

1. Introduction

Dans ce module, nous allons continuer notre discussion sur la manière d'apprendre des stratégies optimales pour guider un agent dans son environnement. Cette fois-ci, nous allons considérer que l'agent n'a pas accès au modèle complet du MDP qui décrit la dynamique de l'environnement. En conséquence, l'agent:

• Ne connait pas les probabilités de transitions,
• Ni les conséquences des actions qu'il peut suivre,
• Ne sait donc pas quels sont les états sur lesquels il peut arriver en suivant des actions spécifiques sur un état particulier

Les fait que l'agent évolue dans un environnement qu'il ne connait pas totalement classe l'apprentissage qu'il va effectuer dans la catégorie de l'apprentissage par renforcement sans modèle (model-free RL).

Les méthodes de Monte Carlo sont basées sur le calcul de la moyenne des récompenses obtenues. Pour s'assurer que les revenus sont bien définis, ces méthodes sont appliquées uniquement sur taches épisodiques. Cela signifie que les expériences sont divisées en épisodes, et que tous les épisodes se terminent éventuellement, cela peu importe les actions qui ont été utilisées. Les estimations des valeurs ainsi que l'estimation des stratégies ne sont mises à jour que lorsqu'un épisode est terminé. Le terme "Monte Carlo" est souvent utilisé pour décrire des méthodes d'estimation qui font appel à de nombreuses composantes aléatoires. Ici, nous utilisons des méthodes basées sur les revenus générés par des épisodes complets (et non sur des revenus partiels, comme nous le verrons sur d'autres méthodes).

Les méthodes de Monte Carlo calculent la moyenne des revenus sur chaque paires d'état-action, comme cela a été fait dans la problématique du bandit manchot (machine à sous). La différence est qu'ici il existe de multiples états, que chaque état agit comme un bandit manchot et que tous ces états sont entrelacés. Cela signifie que les actons prises sur les premiers états vont dépendre des actions prises sur les états suivants au cours d'un même épisode. Du point de vu des premiers états, le problème est donc non stationnaire.

Pour résoudre ce problème de non stationnarité, l'idée est d'utiliser les méthodes générales d'itération des stratégies vues précédemment dans le cadre de la programmation dynamique. Alors que dans ces méthodes, la fonctions des valeurs des états et des actions étaient calculées, elle vont maintenant être apprises. Comme dans le cadre de la programmation dynamique, nous allons considérer les étapes suivantes :

• Prédiction : L'objectif est d'apprendre la fonction des valeurs des états $V\pi$ de l'environnement pour une stratégie $\pi$ suivie par un agent.
• Estimation : Le but est d'estimer la fonction des valeurs d'actions $q_\pi$.
• Contrôle : Finalement, en utilisant les estimations précédentes, l'objectif est ici de trouver des stratégies optimales.

Toutes ces idées sont issues de celles étudiées dans le cadre de la programmation dynamique, et étendues ici sur des cas où ne sont disponibles que des échantillons issus de l'expérience.